| Algorithm | Time Complexity(Worst) | Time Complexity(Average) | Space complexity |
|---|---|---|---|
| Insertion sort | O(n2) | O( n) | O(1) |
| Merge sort | O(nlog(n)) | O( nlog(n)) | O(n) |
| Heapsort | O(n log(n)) | O(n log(n)) | O(1) |
| Quicksort | O(n2) | O(n log(n)) | O(n) |
| Counting sort | O(n log(n)) | O(n) | O(n) |
Conclustion: heapsort and mergesort are asymtotically optimal comparison sort
#Insertion Sort
for index 1 to n as i ,choose the [i]th number as key.
Compare key with the numbers before it
//In this step above, the best case time is n,the worst case is n2.
If numbers > key,
shift it back one
until the find the number is small than key,
put the numbers behind it.
(which actually in coding is the last number’s index who is > key )
Attention：For insertion sort, the array before the Key is always sorted.
#Merge Sort
Merge Algorithm:
Given array A ,start ,mid ,end.
Divide it to two arrays.
For start to end,
compare two array,
put the smaller one on the position of A
Merge Sort Algorithm:
Use recursion to divided array into small pieces
Then merge them
#Heapsort
Use array’s index to build a binary tree
Parent(i) : return [i/2] Left(i):return 2i Right(i):return 2i+1
MAX-HEAP algorithm:
only consider three nodes(parent left right) construct,
put the biggest one on parent
if the biggest one if not parent itself
recursion the biggest one’s index
/**
The step above is necessary because in BUILD-MAX-HEAP process, the parents(which is already sorted as biggest)might change. Because we are doing max-heapify from down to top. /
BUILD-MAX-HEAP algorithm:
for [A.length/2] to 1 as i,
MAX-HEAPIFY(A,i);
HEAPSORT algorithm:
BUILD-MAX-HEAP
continuously swap the heap with last one
and MAX-HEAPIFY remain array.
Implementation: Priority queues
#Quicksort
PARITION algorithm:
choose end as axis ,
for j from start to end-1
if A[i] < axis,
put it from the begin
(starts from i,every swap,i++)
End for loop, swap axis with A[i+1]
//which means before the axis there totall has i numbers < axis
return i+1,which is the new PARITION line
QUICKSORT algorithm:
first partition whole arrays,
get the PARITION line,
use recursion to continue PARITION while(p<r?)
#Counting Sort
Use a new array C,
C[i] contains the number of elements equal to i in array A
Then C[i] contains the number of elements less than or equal to i
Use a new array B as output,B[C[A[j]]] = A[j], C[A[j]] --
#Bucket Sort
类似hash, Array 里面装链表或者list
